package com.cloud.code.牛客网;

import java.util.HashMap;
import java.util.Map;

/**
 * 70. 爬楼梯
 */
public class Test25 {

    public static void main(String[] args) {

        int i = climbStairs(10);
        System.out.println(i);
    }

    public static int climbStairs(int n) {
        Map<Integer,Integer>  map = new HashMap<>();
        return sum(n,map);

    }

    private static int sum(int n, Map<Integer, Integer> map) {
        if(n == 1){
            return 1;
        }

        if(n == 2){
            return 2;
        }

        if(map.get(n) != null){
            return map.get(n);
        }else {
            int i = sum(n - 1,map) + sum(n - 2,map);
            map.put(n,i);
            return i;
        }
    }

}
